package leetcode.sort;

import java.util.*;

/**
 * @Description
 * @Author 26233
 * @Create 2020-12-05 21:26:08
 *
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *  
 *
 * 提示：
 *
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
 * 你可以按任意顺序返回答案。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class LeetCode347_TopKFrequent {

    // 建立K大小的小根堆，然后遍历数组，并调整。因为小根堆堆顶是K堆的最小元素，如果比堆顶小，笔必不是TopK的元素。当大于时，替换堆顶元素，并从堆顶开始调整
    public static int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> itemCount = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer v = itemCount.get(nums[i]);
            if (v == null) {
                itemCount.put(nums[i], 1);
            } else {
                itemCount.put(nums[i], v + 1);
            }
        }

        // 建堆
        int[] smallHeap = new int[k];
        int len = 0;
        Iterator<Integer> iterator = itemCount.values().iterator();
        Set<Map.Entry<Integer, Integer>> entries = itemCount.entrySet();
        Map<Integer, Integer> result = new HashMap<>();
        for (Map.Entry<Integer, Integer> e : entries) {
            Integer v = e.getValue();
            if (len != k) {
                heapfiy(smallHeap, v, len);
                result.put(v, e.getKey());
                len++;
            } else {
                if (v > smallHeap[0]) {
                    result.remove(smallHeap[0]);
                    smallHeap[0] = v;
                    heapfiy(smallHeap);
                }
            }
        }

//        while (iterator.hasNext()){
//            Integer v = iterator.next();
//            if(len != k){
//                heapfiy(smallHeap, v, len);
//                len++;
//            }else{
//                if(v > smallHeap[0]){
//                    smallHeap[0] = v;
//                    heapfiy(smallHeap);
//                }
//            }
//        }
        int[] r = new int[result.values().size()];
        Iterator<Integer> iterator1 = result.values().iterator();
        len = 0;
        while(iterator1.hasNext()){
            r[len++] = iterator1.next();
        }

        return r;
    }


    public static void heapfiy(int[] heap, int v, int index){
        heap[index] = v;
        while(index > 0){
            int tempIndex = (index - 1) / 2;
            if(heap[tempIndex] > heap[index]){
                int tempV = heap[tempIndex];
                heap[tempIndex] = heap[index];
                heap[index] = tempV;
                index = tempIndex;
            }else break;
        }
    }
    public static void heapfiy(int[] heap){
        int index = 0;
        while(index < heap.length){
            int tempLeft = (2 * index + 1);
            int tempRight = (2 * index + 2);
            if(tempLeft < heap.length){
                if(tempRight < heap.length){
                    if(heap[tempLeft] > heap[tempRight] && heap[tempRight] < heap[index]){
                        int tempV = heap[tempRight];
                        heap[tempRight] = heap[index];
                        heap[index] = tempV;
                        index = tempRight;
                    }else if(heap[tempLeft] <= heap[tempRight] && heap[tempLeft] < heap[index]){
                        int tempV = heap[tempLeft];
                        heap[tempLeft] = heap[index];
                        heap[index] = tempV;
                        index = tempLeft;
                    }
                }else{
                    if(heap[tempLeft] < heap[index]){
                        int tempV = heap[tempLeft];
                        heap[tempLeft] = heap[index];
                        heap[index] = tempV;
                        index = tempLeft;
                    }
                }
            }else break;
        }
    }

    public static void main(String[] args) {
        int[] input = {1,1,1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6};
        System.out.println(topKFrequent(input, 3));
    }
}
